#include "DecisionMaker.hpp"
/*@author:黄嘉良
 *@description: 决策类的实现
 *@Time: 2020/04/06
 */

DecisionMaker::DecisionMaker() : round(0) {}
DecisionMaker::DecisionMaker(int M_, int N_)
    : round(0)
{
#ifdef DEBUG
    std::cerr << "M = " << M_ << ", N = " << N_ << endl;
#endif
    top = new int[COL_MAX_NUMBER];
}

DecisionMaker::~DecisionMaker() { delete[] top; }

void DecisionMaker::init(int M_, int N_, int **board_, const int *top_, int noX, int noY, int MAX_DEPTH_)
{
    auto check_restart = [M_, N_, top_]() {
        int count = 0;
        for (int i = 0; i < N_; ++i)
        {
            count += M_ - top_[i];
        }
        if (count <= 1)
            return true;
        else
            return false;
    };
    if (check_restart())
        round = 0;
    M = M_;
    N = N_;
    no_x = noX;
    no_y = noY;
    board = board_;
    std::copy(top_, top_ + N, top);
    if (round == 0)
        MAX_DEPTH = 3;
    else if (round >= 35)
        MAX_DEPTH = 9;
    else
        MAX_DEPTH = 7;
    round++;
}

/*******************************************************/
/********************alpha beta prun********************/
/*******************************************************/
inline int DecisionMaker::get_chess(int x, int y) const
{
    if (x < M && y < N && x >= 0 && y >= 0)
        return board[x][y];
    else
        return -1;
}

inline int DecisionMaker::get_top(int column) const
{
    if (column < N && column >= 0)
        return top[column];
    else
        return -1;
}

/****************************************
 * alpha_beta
 * Function:
 *      alpha-beta剪枝的外部接口，返回最佳的列
 ****************************************/
int DecisionMaker::alpha_beta()
{
    int best_col = -1;        //最佳的列
    int best_score = INT_MIN; //最佳分数
    for (int i = 0; i < N; ++i)
    {
        /*下一步相应的棋*/
        int possible_pos = top[i];
        if (possible_pos <= 0)
            continue;
        board[possible_pos - 1][i] = 2;
        /*如果这一步获胜了*/
        if (machineWin(possible_pos - 1, i, M, N, board))
        {
            return i;
        }
        /*这一步没有获胜*/
        if ((no_y == i) && (no_x == possible_pos - 2))
            top[i] -= 2;
        else
            top[i] -= 1;
        /*计算分数*/
        int score = alpha_beta_prun(1, USER, best_score, INT_MAX);
        if (score > best_score) //这里的大于很关键，不能取等
        {
            best_col = i;
            best_score = score;
        }
        /*恢复棋盘*/
        board[possible_pos - 1][i] = 0;
        if ((no_y == i) && (no_x == possible_pos - 2))
            top[i] += 2;
        else
            top[i] += 1;
    }
    return best_col;
}

/****************************************
 * alpha_beta_prun
 *  Param:
 *      - depth表示递归的深度
 *      - role表示当前节点表示的角色
 *      - max表示所有祖先的最大alpha值（下界）
 *      - min表示所有祖先的最小beta值（上界）
 * Function:
 *      alpha-beta剪枝的递归函数
 ****************************************/
int DecisionMaker::alpha_beta_prun(int depth, Role role, int max, int min)
{
    int local_score = (role == USER) ? INT_MAX : INT_MIN;
    /*Reach the deepest*/
    if (depth == MAX_DEPTH)
        return evaluate();
    /*判断是否平局*/
    if (isTie(N, top))
        return TIE_SCORE;
    /*Iterator the all possible chess*/
    for (int i = 0; i < N; ++i)
    {
        /*在第i列下一步棋子*/
        int possible_pos = top[i];
        if (possible_pos <= 0) //该列已满
            continue;
        board[possible_pos - 1][i] = (role == USER) ? 1 : 2;
        /*判断是否结束，如果某一方直接获胜的话，那么直接返回即可，因为自己和对方一定会走这么一步*/
        if (role == USER && userWin(possible_pos - 1, i, M, N, board))
        {
            board[possible_pos - 1][i] = 0;
            return LOSE_SCORE;
        }
        else if (role == COMPUTER && machineWin(possible_pos - 1, i, M, N, board))
        {
            board[possible_pos - 1][i] = 0;
            return WIN_SCORE;
        }
        /*如果没有直接出现胜负，则修改top数组*/
        if ((no_y == i) && (no_x == possible_pos - 2))
            top[i] -= 2;
        else
            top[i] -= 1;
        /*剪枝进行递归*/
        Role next_role = (role == USER) ? COMPUTER : USER;
        int score = alpha_beta_prun(depth + 1, next_role, max, min);
        /*递归返回后恢复棋盘*/
        board[possible_pos - 1][i] = 0;
        if ((no_y == i) && (no_x == possible_pos - 2))
            top[i] += 2;
        else
            top[i] += 1;
        /*更新数值*/
        if (role == COMPUTER)
        {
            local_score = std::max(local_score, score);
            max = std::max(max, score);
        }
        else // role == USER
        {
            local_score = std::min(local_score, score);
            min = std::min(min, score);
        }
        /*判断剪枝*/
        if (role == USER)
        {
            // USER最后选择的分数一定小于等于score
            if (local_score <= max)
                return local_score;
        }
        else
        {
            // COMPUTER最后选择的分数一定大于score
            if (local_score >= min)
                return local_score;
        }
    }
    /*没有因为提前的剪枝而返回，因此按照角色返回值*/
    return local_score;
}

/****************************************
 * evaluate
 * Function:
 *      评估当前的布局，返回一个分数
 *      不必考虑获胜或者平局的情况，也就是四字相连不必考虑
 *      对于COMPUTER而言：
 *      棋子相连的分数比较高，也就是棋子比较集中相对好一些
 *      一段或者两端被堵住的棋子分数会上升
 ****************************************/
int DecisionMaker::evaluate() const
{
    int score = 0;
    const int weight[] = {0, 1, 4, 9};
    //下面这个lambda表达式用来统计各个方向的信息
    //例如x_offset = 0, y_offset = 1表示水平方向
    //x_offset = -1, y_offset = 1表示左下到右上方向
    auto check_field = [this, weight](int row, int col, int x_offset, int y_offset, Role role) {
        const int chess_id = (role == USER) ? 1 : 2; //统计方role的棋子编号
        int direct_ = 1;                             //一次搜索棋子相连的个数
        int score_ = 0;                              //搜索得分
        //先搜索正侧的（例如水平方向的话，先搜索右侧）
        for (int r = row + x_offset, c = col + y_offset; (r <= row + 3 * x_offset) && (c <= col + 3 * y_offset);
             r += x_offset, c += y_offset)
        {
            int chess_num = get_chess(r, c);
            if (chess_num == chess_id) //该位置是统计方棋子
                direct_ += 1;
            else if (chess_num == 0) //该位置没有棋子
            {
                score_ += weight[direct_];
                direct_ = 0;
            }
            else
            {
                direct_ = direct_ == 0 ? 0 : direct_ - 1;
                break;
            }
        }
        score_ += weight[direct_];
        direct_ = 1;
        //搜索反侧的（例如水平方向先搜索左侧）
        for (int r = row - x_offset, c = col - y_offset; (r >= row - 3 * x_offset) && (c >= col - 3 * y_offset);
             r -= x_offset, c -= y_offset)
        {
            int chess_num = get_chess(r, c);
            if (chess_num == chess_id)
                direct_ += 1;
            else if (chess_num == 0)
            {
                score_ += weight[direct_];
                direct_ = 0;
            }
            else
            {
                direct_ = direct_ == 0 ? 0 : direct_ - 1;
                break;
            }
        }
        score_ += weight[direct_];
        return score_;
    };
    /*只统计处于顶端的棋子信息*/
    for (int col = 0; col < N; ++col)
    {
        int row = top[col];
        int chess_num = get_chess(row, col);
        if (chess_num == 1)
        {
            score -= check_field(row, col, 0, 1, USER);
            score -= check_field(row, col, 1, 0, USER);
            score -= check_field(row, col, 1, 1, USER);
            score -= check_field(row, col, -1, 1, USER);
        }
        else if (chess_num == 2)
        {
            score += check_field(row, col, 0, 1, COMPUTER);
            score += check_field(row, col, 1, 0, COMPUTER);
            score += check_field(row, col, 1, 1, COMPUTER);
            score += check_field(row, col, -1, 1, COMPUTER);
        }
    }
    return score;
}

/*UCT Search*/
int DecisionMaker::UCT_search(clock_t start)
{
    static UCTSearch searcher(M, N, no_x, no_y);
    //由于类是静态变量，每次需要更新
    searcher.reset(M, N, board, top, no_x, no_y);
    int res = searcher.search(start);
    return res;
}